package comprehensive;

public class Exercises12 {
    // 37、解数独
    boolean[][] row; // 用于标记 行 中对应得到num数字是否出现过
    boolean[][] col; // 用于标记 列 中对应得到num数字是否出现过
    boolean[][][] grid; // 用于标记 3x3的小宫格 中对应得到num数字是否出现过

    public void solveSudoku(char[][] board) {
        // 初始化
        row = new boolean[9][10];
        col = new boolean[9][10];
        grid = new boolean[3][3][10];

        // 对于一开始给的 board中的数独棋盘中的每行每列和每一个小宫格中出现的数字进行初始化记录，方便后面进行放入数字时进行查看是否可以放入
        for(int i = 0; i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    // 每i行中 出现的 num数字进行初始化
                    row[i][num] = true;
                    // 每i行的第j列的第i个位置出现的 num数字进行
                    col[j][num] = true;
                    // 对于3x3的小九宫格进行初始化
                    grid[i / 3][j / 3][num] = true;
                }
            }
        }

        dfs(board);
    }

    public boolean dfs(char[][] board) {
        for(int i = 0;i < 9;i++) {
            for(int j = 0;j < 9;j++) {
                if(board[i][j] == '.') { // 字符之间的比较可以使用 ==
                    for(int num = 1;num <= 9;num++) {
                        if(!row[i][num] && !col[j][num] && !grid[i/3][j/3][num]) {
                            // 进行放入数据num
                            board[i][j] = (char)('0' + num);
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = true;
                            if(dfs(board) == true) {
                                // 跳转会回上一个
                                return true;
                            }

                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i/3][j/3][num] = false;
                        }
                    }
                    // 在这时候就是 1-9都不能放入，就返回false，只有1-9数字对于任何位置都放不进入的时候，才会为false
                    return false;
                }
            }
        }
        // 9行9列都判断结束了，那么这时候就一定是正确的，不会判断出 '.' 这个字符
        return true;
    }
}
